/**
 * @file pt_heap4.c
 * @author Linquan  
 * @brief 
 * @version 1.0
 * @date 2024-06-13
 * 
 * @copyright Copyright (c) 2024
 * 
 */


#include "FreeRTOS_heap4.h"
#if  FREE_RTOS_HEAP_4

#include <stdlib.h>
#include <stdint.h>

 #include "color_print.h"

// 总共栈大小，移植敏感
#define TOTAL_HEAP_SIZE 1024
// 字节对齐，移植敏感
#define BYTE_ALIGNMENT 8
// 断言，移植敏感
#define HEAP_ASSERT(expr)  ASSERT_PARAM(expr,"request size is not Byte alignment ")

#define BYTE_ALIGNMENT_MASK BYTE_ALIGNMENT - 1

#define MINIMUM_BLOCK_SIZE  ( ( size_t ) ( heap_struct_size << 1 ) )

#define BITS_PER_BYTE         ( ( size_t ) 8 )

static uint8_t s_heap[ TOTAL_HEAP_SIZE ];

typedef struct A_BLOCK_LINK
{
    struct A_BLOCK_LINK * next_free_block; /*<< The next free block in the list. */
    size_t block_size;                     /*<< The size of the free block. */
} block_link_t;


#ifndef USE_MALLOC_FAILED_HOOK
#define USE_MALLOC_FAILED_HOOK 0
#endif

#if USE_MALLOC_FAILED_HOOK
__attribute__((weak)) void app_malloc_failed_hook(void)
{
    for (;;)
        ;
}
#endif

__attribute__((weak)) void heap_lock(void)
{
    
}

__attribute__((weak)) void heap_unlock(void)
{
   
}

/*-----------------------------------------------------------*/

static void insert_block_into_free_list( block_link_t * block_to_insert ) ;


static void heap_init( void );

/*-----------------------------------------------------------*/

/* The size of the structure placed at the beginning of each allocated memory
 * block must by correctly byte aligned. */
static const size_t heap_struct_size = ( sizeof( block_link_t ) + ( ( size_t ) ( BYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) BYTE_ALIGNMENT_MASK );

/* Create a couple of list links to mark the start and end of the list. */
static block_link_t start, * end = NULL;

/* Keeps track of the number of calls to allocate and free memory as well as the
 * number of free bytes remaining, but says nothing about fragmentation. 
 * 记录分配和释放内存的调用次数，以及剩余的空闲字节数，但没有提到碎片化的问题
 */
static size_t free_bytes_remaining = 0U;                /* 空闲空间大小 */
static size_t minimum_ever_free_bytes_remaining = 0U;   /* 空闲空间曾经达到的最小的大小*/
static size_t number_of_successful_allocations = 0;
static size_t number_of_successful_free = 0;

/* Gets set to the top bit of an size_t type.  When this bit in the block_size
 * member of an block_link_t structure is set then the block belongs to the
 * application.  When the bit is free the block is still part of the free heap
 * space. 
 * 用于设置block_link_t的节点中的block_size的最高位
 * 该位被设置时，认为该块属于应用程序，是被分配过的；
 * 当该位是空闲的，该块仍然是空闲空间的一部分，未被分配*/
static size_t block_allocate_bit = 0;

/*-----------------------------------------------------------*/

void * pt_malloc( size_t size )
{
    block_link_t * block, * previous_block, * new_block_link;
    void * ret = NULL;

    heap_lock();
    {

        if( end == NULL )
        {
            heap_init();
        }

        /* 判断需要分配的大小，是否超过系统能够管理的最大地址 */
        if( ( size & block_allocate_bit ) == 0 )
        {
            if( ( size > 0 ) && 
                ( ( size + heap_struct_size ) >  size ) ) /* Overflow check */
            {
                /* 分配的大小加上 block_link_t的大小 */
                size += heap_struct_size;

                /* Ensure that blocks are always aligned. */
                if( ( size & BYTE_ALIGNMENT_MASK ) != 0x00 )
                {
                    /* Byte alignment required. Check for overflow. 
                    *  检查 size的大小加上凑成字节对齐的大小后，是否出现溢出造成，值变小的情况
                    */
                    if( ( size + ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) ) ) 
                            > size )
                    {
                        /* 把请求的大小凑成字节对齐的大小 */
                        size += ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) );
                        HEAP_ASSERT( ( size & BYTE_ALIGNMENT_MASK ) == 0 );
                    }
                    else
                    {
                        size = 0;
                    }  
                }
            } 
            else 
            {
                size = 0;
            }

            if( ( size > 0 ) && ( size <= free_bytes_remaining ) )
            {
                /* Traverse the list from the start	(lowest address) block until
                 * one of adequate size is found. */
                previous_block = &start;
                block = start.next_free_block;

                while( ( block->block_size < size ) && ( block->next_free_block != NULL ) )
                {
                    previous_block = block;
                    block = block->next_free_block;
                }

                /* If the end marker was reached then a block of adequate size
                 * was not found. */
                if( block != end )
                {
                    /* Return the memory space pointed to - jumping over the
                     * block_link_t structure at its start. */
                    ret = ( void * ) ( ( ( uint8_t * ) previous_block->next_free_block ) + heap_struct_size );

                    /* This block is being returned for use so must be taken out
                     * of the list of free blocks. */
                    previous_block->next_free_block = block->next_free_block;

                    /* If the block is larger than required it can be split into
                     * two. */
                    if( ( block->block_size - size ) > MINIMUM_BLOCK_SIZE )
                    {
                        /* This block is to be split into two.  Create a new
                         * block following the number of bytes requested. The void
                         * cast is used to prevent byte alignment warnings from the
                         * compiler. */
                        new_block_link = ( void * ) ( ( ( uint8_t * ) block ) + size );
                        HEAP_ASSERT( ( ( ( size_t ) new_block_link ) & BYTE_ALIGNMENT_MASK ) == 0 );

                        /* Calculate the sizes of two blocks split from the
                         * single block. */
                        new_block_link->block_size = block->block_size - size;
                        block->block_size = size;

                        /* Insert the new block into the list of free blocks. */
                        insert_block_into_free_list( new_block_link );
                    }

                    free_bytes_remaining -= block->block_size;

                    if( free_bytes_remaining < minimum_ever_free_bytes_remaining )
                    {
                        minimum_ever_free_bytes_remaining = free_bytes_remaining;
                    }
                    /* The block is being returned - it is allocated and owned
                     * by the application and has no "next" block.
                     * 把这个块的节点中大小的最高位设为1,认为该节点已被分配，
                     * 然后把后续节点指向NULL，这个块的节点就释放了。
                     */
                    block->block_size |= block_allocate_bit;
                    block->next_free_block = NULL;
                    number_of_successful_allocations++;
                }
            }
        }
    }
    ( void ) heap_unlock();

    #if ( USE_MALLOC_FAILED_HOOK == 1 )
    {
        if ( ret == NULL ) {
            app_malloc_failed_hook();
        }
    }
    #endif /* if ( USE_MALLOC_FAILED_HOOK == 1 ) */

    HEAP_ASSERT( ( ( ( size_t ) ret ) & ( size_t ) BYTE_ALIGNMENT_MASK ) == 0 );
    return ret;
}
/*-----------------------------------------------------------*/

void pt_free( void * pv )
{
    uint8_t * puc = ( uint8_t * ) pv;
    block_link_t * link;

    if( pv != NULL )
    {
        /* The memory being freed will have an block_link_t structure immediately
         * before it. */
        puc -= heap_struct_size;

        /* This casting is to keep the compiler from issuing warnings. */
        link = ( void * ) puc;

        /* Check the block is actually allocated. */
        HEAP_ASSERT( ( link->block_size & block_allocate_bit ) != 0 );
        HEAP_ASSERT( link->next_free_block == NULL );

        if( ( link->block_size & block_allocate_bit ) != 0 )
        {
            if( link->next_free_block == NULL )
            {
                /* The block is being returned to the heap - it is no longer
                 * allocated. 
                 * 将块大小的最高位清零，代表该块恢复成空闲状态，不再被分配 
                 * */
                link->block_size &= ~block_allocate_bit;

                heap_lock();
                {
                    /* Add this block to the list of free blocks. */
                    free_bytes_remaining += link->block_size;
                    insert_block_into_free_list( ( ( block_link_t * ) link ) );
                    number_of_successful_free++;
                }
                ( void ) heap_unlock();
            }
        }
    }
}
/*-----------------------------------------------------------*/

size_t pt_get_free_size( void )
{
    return free_bytes_remaining;
}
/*-----------------------------------------------------------*/

size_t pt_get_min_ever_free_heap_size( void )
{
    return minimum_ever_free_bytes_remaining;
}
/*-----------------------------------------------------------*/

void pt_heap_init( void )
{
    /* This just exists to keep the linker quiet. */
}
/*-----------------------------------------------------------*/

static void heap_init( void ) 
{
    block_link_t * frist_free_block;
    uint8_t * aligned_heap;
    size_t address;
    size_t total_heap_size = TOTAL_HEAP_SIZE;

    /* Ensure the heap starts on a correctly aligned boundary. */
    address = ( size_t ) s_heap;

    /* heap的地址非字节对齐 */
    if( ( address & BYTE_ALIGNMENT_MASK ) != 0 )
    {
        address += ( BYTE_ALIGNMENT - 1 );
        address &= ~( ( size_t ) BYTE_ALIGNMENT_MASK );
        /* 计算后的起始地址 - 原分配的堆的起始地址 = 需要从堆总大小里删掉的部分 */
        total_heap_size -= address - ( size_t ) s_heap;
    }

    aligned_heap = ( uint8_t * ) address;

    /* start is used to hold a pointer to the first item in the list of free
     * blocks.  The void cast is used to prevent compiler warnings. */
    start.next_free_block = ( void * ) aligned_heap;
    start.block_size = ( size_t ) 0;

    /* end is used to mark the end of the list of free blocks and is inserted
     * at the end of the heap space. */
    /* 在heap的末尾，往前留一个block_link_t的大小，然后再按照地址字节对齐往后移动一点 
        由此计算得到可用的堆空间大小
    */
    address = ( ( size_t ) aligned_heap ) + total_heap_size;
    address -= heap_struct_size;
    address &= ~( ( size_t ) BYTE_ALIGNMENT_MASK );
    end = ( void * ) address;
    end->block_size = 0;
    end->next_free_block = NULL;

    /* To start with there is a single free block that is sized to take up the
     * entire heap space, minus the space taken by end. 
     * 最初，有一个单一的空闲块，它的尺寸占据了整个堆空间，减去了被 end 占用的空间
     * 这个单一空闲块，是链接到start节点上，并由start节点记录块长度
     */
    frist_free_block = ( void * ) aligned_heap;
    frist_free_block->block_size = address - ( size_t ) frist_free_block;
    frist_free_block->next_free_block = end;

    /* Only one block exists - and it covers the entire usable heap space. */
    minimum_ever_free_bytes_remaining = frist_free_block->block_size;
    free_bytes_remaining = frist_free_block->block_size;

    /* Work out the position of the top bit in a size_t variable. 
        计算一下 size_t 的位数大小，用于确定当前系统位数
    */
    block_allocate_bit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * BITS_PER_BYTE ) - 1 );
}
/*-----------------------------------------------------------*/

static void insert_block_into_free_list( block_link_t * block_to_insert ) /*  */
{
    block_link_t * itertator;
    uint8_t * puc;

    /* Iterate through the list until a block is found that has a higher address
     * than the block being inserted. 
     * 从头遍历链表，找到一个比当前插入的块的地址 低的块，把当前插入的块接到这个块后边
     */
    for( itertator = &start; itertator->next_free_block < block_to_insert; itertator = itertator->next_free_block )
    {
        /* Nothing to do here, just iterate to the right position. */
    }

    /* Do the block being inserted, and the block it is being inserted after
     * make a contiguous block of memory? 
     * 正在插入的块和插入点的块是否形成了一块连续的内存，
     * 判断条件是：插入的块的地址+插入块的大小 == 插入点的地址 ，相当于插入点的地址在插入块的后边
     */
    puc = ( uint8_t * ) itertator;

    if( ( puc + itertator->block_size ) == ( uint8_t * ) block_to_insert )
    {
        itertator->block_size += block_to_insert->block_size;
        block_to_insert = itertator;
    }

    /* Do the block being inserted, and the block it is being inserted before
     * make a contiguous block of memory? 
     * 插入块的地址 + 插入块的大小 == 插入点后边的块的地址 ，就认为插入点后边块的和 插入的块是相邻的
     * 也就是 插入点在插入块的前边（包含了上边那个判断已经合并过一次的情况）
     * */
    puc = ( uint8_t * ) block_to_insert;

    if( ( puc + block_to_insert->block_size ) == ( uint8_t * ) itertator->next_free_block )
    {
        if( itertator->next_free_block != end )
        {
            /* Form one big block from the two blocks. */
            block_to_insert->block_size += itertator->next_free_block->block_size;
            block_to_insert->next_free_block = itertator->next_free_block->next_free_block;
        }
        else
        {
            block_to_insert->next_free_block = end;
        }
    }
    else
    {
        block_to_insert->next_free_block = itertator->next_free_block;
    }

    /* If the block being inserted plugged a gab, so was merged with the block
     * before and the block after, then it's next_free_block pointer will have
     * already been set, and should not be set here as that would make it point
     * to itself. */
    if( itertator != block_to_insert )
    {
        itertator->next_free_block = block_to_insert;
    }
}




#endif


